//
// Created by Bianwy on 2024/3/3.
//
#include <iostream>
#include <stack>

using namespace std;
// 155. 最小栈
// 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
// 实现 MinStack 类:
// MinStack() 初始化堆栈对象。
// void push(int val) 将元素val推入堆栈。
// void pop() 删除堆栈顶部的元素。
// int top() 获取堆栈顶部的元素。
// int getMin() 获取堆栈中的最小元素。
class MinStack {
private:
    stack<int> data_stack;  // 数据栈
    stack<int> min_stack;   // 最小栈，栈顶是栈中元素最小值，单调栈（非递增）
public:
    MinStack() {

    }
    // 入栈
    void push(int val) {
        data_stack.push(val);   // 首先将数据放入数据栈
        if(min_stack.empty() || val <= min_stack.top()) // 放入最小栈
            min_stack.push(val);
    }
    // 出栈
    void pop() {
        if(min_stack.top() == data_stack.top())
            min_stack.pop();
        data_stack.pop();
    }
    // 取栈顶
    int top() {
        return data_stack.top();
    }
    // 取栈中元素最小值
    int getMin() {
        return min_stack.top();
    }
};

int main() {
    auto *minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl; // 返回-3
    minStack->pop();
    cout << minStack->top() << endl;    // 返回0
    cout << minStack->getMin() <<endl;  // 返回-2
    return 0;
}

